package com.atwulidun.recursion;

// 问题描述：有编号为 A、B、C、D、E 的 5 本书，以及 5 个人，每本书可以分给每一个对该书有兴趣的人阅读，
// 且每个人都只能分到一本自己感兴趣的书。问当给定 5 个人对 5 本书的感兴趣情况时，怎样分配这 5 本书才能让每个人都开始阅读。
// 思路：与 N 皇后问题几乎一致，每次都尝试给第 p 个人从 5 本书中分出他感兴趣的一本，若不能构成最终解，则撤销回溯到上一个人（即第 p – 1 个人）的分配。
// int bookCounts 表示书的总数量，与总人数相等
// int like [p] [b] = 1 表示第 p 个人喜欢读第 b 本书，即具体的问题初始条件；
// int given [b] = p 表示第 b 本书分给了第 p 个人，即保存解的标识数组。
public class AllocateBooks {
    private int[][] like;
    private int[] given = {-1, -1, -1, -1, -1};// -1表示该本书没有被分出去
    private int bookNum = 5;

    public static void main(String[] args) {
        int[][] like = new int[][]{
                { 0, 0, 1, 1, 0 },
                { 1, 1, 0, 0, 1 },
                { 0, 1, 1, 0, 1 },
                { 0, 0, 0, 1, 0 },
                { 0, 1, 0, 0, 1 }};
        AllocateBooks allocateBooks = new AllocateBooks(like);
        allocateBooks.allocateBooks(0, 0, allocateBooks.bookNum);
    }
    // 实例化时传入描述每个人对书感兴趣情况的二维数组
    public AllocateBooks(int[][] like) {
        this.like = like;
    }

    // 回溯方法(注意：人对书进行选择)
    public void allocateBooks(int person, int bookNumStart, int bookNumEnd) {
        if (person == bookNum) {
            for (int i = 0; i < given.length; i++) {
                System.out.println("第" + (i + 1) + "本书分给了第" + (given[i] + 1) + "个人");
            }
            System.out.println();
            return;
        }
        for (int i = bookNumStart; i < bookNumEnd; i++) {
            // 进行剪枝判断，过滤掉不符合条件的选择
            // 如果当前的人喜欢当前书并且当前书未被借出的话，就把当前书分给当前人，并且让下一个人进行选择
            if (like[person][i] == 1 && given[i] == -1) {
                // 进行选择
                given[i] = person;
                // 递归，让下一个人进行选择
                allocateBooks(person + 1, bookNumStart, bookNumEnd);
                // 撤销，不影响当前人对下一本书的选择
                given[i] = -1;
            } else {
                // 如果判断条件不满足，则让当前人直接去选择下一本书
//                continue;
            }
        }
    }
}
